package acwing;

import java.io.*;
import java.util.*;

public class A850 {
    static final int N = 150010; // [补充] Java数组需要更大，避免越界
    static int[] h = new int[N], e = new int[N], ne = new int[N], w = new int[N];
    static int idx;
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N]; // 若为true，说明节点的最短路径已确定
    static int n, m;

    // [补充] Java中优先队列需要自定义比较器
    static PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] - b[0]);

    // 添加边：x指向y，权重为c
    static void add(int x, int y, int c) {
        w[idx] = c;
        e[idx] = y;
        ne[idx] = h[x];
        h[x] = idx++;
    }

    static int dijkstra() {
        Arrays.fill(dist, 0x3f3f3f3f); // 初始化距离为“无穷大”
        dist[1] = 0;
        heap.offer(new int[]{0, 1}); // 小根堆按距离排序

        while (!heap.isEmpty()) {
            int[] t = heap.poll();
            int ver = t[1], distance = t[0];

            if (st[ver]) continue; // 已确定最短路径则跳过
            st[ver] = true;

            // 遍历邻接边
            for (int i = h[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > distance + w[i]) { // 松弛操作
                    dist[j] = distance + w[i];
                    heap.offer(new int[]{dist[j], j});
                }
            }
        }
        return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        Arrays.fill(h, -1); // 初始化邻接表头指针为-1（类似C++的-1）

        String[] s = br.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);

        while (m-- > 0) {
            String[] edge = br.readLine().split(" ");
            int x = Integer.parseInt(edge[0]);
            int y = Integer.parseInt(edge[1]);
            int c = Integer.parseInt(edge[2]);
            add(x, y, c);
        }

        System.out.println(dijkstra());
    }
}